package com.leetcode.algorithm.y19.m04;

import com.leetcode.algorithm.common.TreeNode;

/**
 * leetcode-cn.com
 * 
 * (done)110. 平衡二叉树
 * (done)108. 将有序数组转换为二叉搜索树
 * (done)220. 存在重复元素 III
 * @author: jie.deng
 * @time: 2019年4月8日 下午7:36:46
 */
public class MySolution0409 {
    
    /**
     * 110. 平衡二叉树
     * 
     * 给定一个二叉树，判断它是否是高度平衡的二叉树。
     * 
     * 本题中，一棵高度平衡二叉树定义为：
     * 
     * 一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
     * 
     * 示例 1:
     * 
     * 给定二叉树 [3,9,20,null,null,15,7]
     * 
     *     3
     *    / \
     *   9  20
     *     /  \
     *    15   7
     * 返回 true 。
     * 
     * 示例 2:
     * 
     * 给定二叉树 [1,2,2,3,3,null,null,4,4]
     * 
     *        1
     *       / \
     *      2   2
     *     / \
     *    3   3
     *   / \
     *  4   4
     * 返回 false 。
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        int h = getHeight(root);
        return h != -1;
    }

    /**
     * 若平衡二叉树,返回树的高度；若非平衡二叉树，返回-1。
     * @param root
     * @return
     */
    private int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int hl = getHeight(root.left);
        int hr = getHeight(root.right);
        if (hl == -1 || hr == -1 || Math.abs(hl - hr) > 1) {
            return -1;
        }
        return Math.max(hl, hr) + 1;
    }
    

    /**
     * 108. 将有序数组转换为二叉搜索树
     * 
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     * 
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     * 
     * 示例:
     * 
     * 给定有序数组: [-10,-3,0,5,9],
     * 
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     * 
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     * 
     * @param nums
     * @return
     */
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length);
    }

    private TreeNode sortedArrayToBST(int[] nums, int fromIdx, int toIdx) {
        if (fromIdx >= toIdx) {
            return null;
        }
        int mid = (fromIdx + toIdx - 1) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, fromIdx, mid);
        root.right = sortedArrayToBST(nums, mid + 1, toIdx);
        return root;
    }
    
    /**
     * 220. 存在重复元素 III
     * 
     * 给定一个整数数组，判断数组中是否有两个不同的索引 i 和 j，使得 nums [i] 和 nums [j] 的差的绝对值最大为 t，并且 i 和 j 之间的差的绝对值最大为 ķ。
     * 
     * 示例 1:
     * 
     * 输入: nums = [1,2,3,1], k = 3, t = 0
     * 输出: true
     * 示例 2:
     * 
     * 输入: nums = [1,0,1,1], k = 1, t = 2
     * 输出: true
     * 示例 3:
     * 
     * 输入: nums = [1,5,9,1,5,9], k = 2, t = 3
     * 输出: false
     * @param nums
     * @param k
     * @param t
     * @return
     */
    public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums == null || nums.length < 2 || k <= 0) {
            return false;
        }
        TreeNode root = new TreeNode(nums[0]);
        for (int idx = 1; idx < nums.length && idx <= k; idx++) {
            int val = nums[idx];
            if (!insertIntoBST(root, val, t)) {
                return true;
            }
        }
        for (int idx = k + 1; idx < nums.length; idx++) {
            int val = nums[idx];
            root = deleteFromBST(root, nums[idx - k - 1]);
            if (!insertIntoBST(root, val, t)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 在二叉搜索树中删除指定结点
     * @param root
     * @param val
     * @return
     */
    private TreeNode deleteFromBST(TreeNode root, int key) {
        if (root == null) {
            return null;
        }
        TreeNode keyNode = null; // key对应的结点
        TreeNode parentNode = null; // keyNode的父结点
        TreeNode cur = root;
        while (cur != null && cur.val != key) {
            parentNode = cur;
            if (cur.val > key) {
                cur = cur.left;
            } else if (cur.val < key) {
                cur = cur.right;
            }
        }
        keyNode = (cur == root && cur.val != key) ? null : cur;
        if (keyNode == null) {
            // 没找到待删除的结点
            return root;
        }

        TreeNode newKey = null; // 用来替换待删除的结点
        if (keyNode.left == null || keyNode.right == null) {
            // 待删除的结点 只有左孩子结点 或者 只有右孩子结点 或者 没有孩子结点 的情况 : 以孩子结点替换待删除的结点
            newKey = keyNode.left == null ? keyNode.right : keyNode.left; // childNode为keyNode的孩子结点，可能为null
        } else {
            // 待删除的结点 有左孩子和右孩子
            // 以左孩子的最大结点替换掉待删除的结点
            cur = keyNode.left;
            TreeNode pre = null;
            while (cur.right != null) {
                pre = cur;
                cur = cur.right;
            }
            newKey = cur;
            if (pre != null) {
                pre.right = null; // 找到了左孩子的最大结点,解除其与父结点的关系
            }
            newKey.right = keyNode.right; // keyNode的right孩子结点作为maxLeft的右孩子

            cur = newKey;
            while (cur != keyNode.left && cur.left != null) {
                cur = cur.left;
            }
            if (cur != keyNode.left) {
                cur.left = keyNode.left; // keyNode的left孩子结点作为 maxLeft的最左孩子
            }
        }
        if (parentNode == null) {
            return newKey;
        } else if (parentNode.val < key) {
            // 待删除的结点为parentNode的右孩子结点
            parentNode.right = newKey;
        } else if (parentNode.val > key) {
            parentNode.left = newKey;
        }
        return root;        
    }

    /**
     * 在二叉搜索树中插入结点
     * 
     * @param root
     * @param val
     * @param t
     * @return 如果待插入的结点 val与树中结点的差的绝对值 <= t，则不插入数据返回false；其他情况插入并返回true
     */
    private boolean insertIntoBST(TreeNode root, int val, int t) {
        TreeNode node = new TreeNode(val); // 新结点
        TreeNode pre = null;
        TreeNode cur = root;
        while (cur != null && Math.abs((long) val - (long) cur.val) > (long) t) {
            pre = cur;
            if (cur.val > val) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        if (cur == null) {
            // 叶子结点，作为pre的孩子结点插入到树中
            if (pre.val > val) {
                pre.left = node;
            } else {
                pre.right = node;
            }
            return true;
        }
        return false;
    }
}
